package 栈队列与哈希表;

import java.util.Stack;

/**
 * 翻转（也叫颠倒）栈的所有元素，如输入栈{1, 2, 3, 4, 5}。
 * 其中，1处在栈顶，翻转之后的栈为{5, 4, 3, 2, 1}，5处在栈顶
 */
public class C如何翻转栈的所有元素 {
    /**
     * 分析解答：
     * 最容易想到的办法是，申请一个额外的队列，先把栈中的元素依次出栈放到队列里，然后把队列里的元素按照出队列顺序入栈，
     * 这样就可以实现栈的翻转，这种方法的缺点是需要申请额外的空间存储队列，
     * 因此，空间复杂度较高。下面介绍一种空间复杂度较低的递归的方法。
     * <p>
     * 递归程序有两个关键因素需要注意：递归定义和递归终止条件。经过分析后，很容易得到该问题的递归定义和递归终止条件。
     * <p>
     * 递归定义：将当前栈的最底元素移到栈顶，其他元素顺次下移一位，然后对不包含栈顶元素的子栈进行同样的操作。
     * 终止条件：递归下去，直到栈为空。递归的调用过程如下图所示。
     */

    public static void move_bottonm_to_top(Stack<Integer> s) {
        if (s.empty()) {
            return;
        }
        int top1 = s.peek();
        s.pop();//弹出栈顶元素
        if (!s.empty()) {
            //递归处理不包含栈顶元素的子栈
            move_bottonm_to_top(s);
            int top2 = s.peek();
            s.pop();
            //交换栈顶元素与子栈栈顶元素
            s.push(top1);
            s.push(top2);
        } else {
            s.push(top1);
        }
    }

    public static void reverse_stack(Stack<Integer> s) {
        if (s.empty()) {
            return;
        }
        //把栈低元素移动找栈顶
        move_bottonm_to_top(s);
        int top = s.peek();
        s.pop();
        //递归处理子栈
        reverse_stack(s);
        s.push(top);
    }

    public static void main(String[] args) {
        Stack<Integer> s = new Stack<>();
        s.push(5);
        s.push(4);
        s.push(3);
        s.push(2);
        s.push(1);

        reverse_stack(s);
        System.out.println("翻转后出栈顺序为：");
        while (!s.empty()) {
            System.out.print(s.peek() + " ");
            s.pop();
        }
    }
}

/**
 * 分析与解答：很容易通过对上述方法进行修改得到栈的排序算法。
 * 主要思路：首先对不包含栈顶元素的子栈进行排序，如果栈顶元素大于子栈的栈顶元素，则交换这两个元素。
 * 因此，在上述方法中，只需要在交换栈顶元素与子栈顶元素时增加一个条件判断即可实现栈的排序
 */
class CC如何给栈排序 {

    public static void move_bottom_to_top(Stack<Integer> s) {
        if (s.empty()) {
            return;
        }
        int top1 = s.peek();
        s.pop();
        if (!s.empty()) {
            //递归处理不包含栈顶元素的子栈
            move_bottom_to_top(s);
            int top2 = s.peek();
            if (top1 > top2) {
                s.pop();
                //交换栈顶元素与子栈栈顶元素
                s.push(top1);
                s.push(top2);
                return;
            }
        }
        s.push(top1);
    }

    public static void sort_stack(Stack<Integer> s) {
        if (s.empty()) {
            return;
        }
        //把栈低元素地洞到栈顶
        move_bottom_to_top(s);
        int top = s.peek();
        s.pop();
        //递归处理子栈
        sort_stack(s);
        s.push(top);
    }

    public static void main(String[] args) {
        Stack<Integer> s = new Stack<>();
        s.push(5);
        s.push(4);
        s.push(3);
        s.push(2);
        s.push(1);
        sort_stack(s);
        System.out.println("翻转后出栈顺序为：");
        while (!s.empty()) {
            System.out.print(s.peek() + " ");
            s.pop();
        }
    }
}